//41.缺失的第一个正数
//https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //负数一定被置为大于n的正数
        //小于等于n的正数对应映射下标位置一定为负数
        //最后 没有被映射为负数的下标一定是没有出现的数
        //返回下标+1即为最小数
        int n = nums.size();
        //将所有负数置为n+1 
        for(int& m:nums) if(m <= 0) m = n+1;
        
        //遍历每个 小于等于n的正数 将对应位置置为负数
        for(int i = 0;i<n;++i)
        {
            int val = abs(nums[i]);
            if(val <= n) nums[val-1]=-abs(nums[val-1]);
        }
        //遍历数组 没有出现的最小正数其下标一定为正数
        for(int i = 0;i<n;++i) if(nums[i] > 0) return i+1;
        return n+1;
    }
};